package class07;

/**
 * @description: 判断一棵树是否是二叉搜索树
 * @time: 2021/7/17 10:45
 * @author: lhy
 */
public class SearchedBinaryTree {
    public static class Info{
        int min;
        int max;
        boolean isSearched;
        public Info(boolean isSearched, int max, int min){
            this.isSearched = isSearched;
            this.max = max;
            this.min = min;
        }
    }
    public boolean isSearched(TreeNode root){
        return process(root).isSearched;
    }

    private Info process(TreeNode root) {
        if (root == null) {
            return null;
        }
        Info leftInfo = process(root.left);
        Info rightInfo = process(root.right);
        int min = root.val;
        int max = root.val;
        if (leftInfo != null){
            min = Math.min(leftInfo.min, min);
            max = Math.max(leftInfo.max,max);
        }
        if (rightInfo != null) {
            min = Math.min(rightInfo.min, min);
            max = Math.max(rightInfo.max,max);
        }
        boolean isSearched = false;
        boolean leftIsSearched = leftInfo == null || leftInfo.isSearched;
        boolean rightIsSearched = rightInfo == null || rightInfo.isSearched;
        boolean leftMaxLessRoot = leftInfo == null || (leftInfo.max < root.val);
        boolean rightMinMostRoot = rightInfo == null || (rightInfo.min > root.val);
        if (leftIsSearched && rightIsSearched && leftMaxLessRoot && rightMinMostRoot){
            isSearched = true;
        }
        return new Info(isSearched,max,min);
    }
}
